143. 重排链表

Similar Question

leading to the advanced question

Solution Tips

方案一: 快慢指针找中点 + 翻转后半段 + 合并链表

var reorderList = function(head) {
    if (head === null || head.next === null) return head;
    const dummy = new Node(0);
    dummy.next = head;

    // 找到链表中点
    let prevSlow = dummy;
    let slow = head;
    let fast = head;
    while (fast !== null && fast.next !==null) {
        fast = fast.next.next;
        slow = slow.next;
        prevSlow = prevSlow.next;
    }

    // 断开
    let prev = null;
    let cur = slow;
    prevSlow.next = null;
    // 翻转后半段
    while (cur !== null) {
        const next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }

    // 然后 merge
    let l1 = head;
    let l2 = prev;
    while (l2 !== null) {
        const next = l1.next;
        l1.next = l2;
        l1 = l2;
        l2 = next;
    }

    return dummy.next;
};

方案二: 双向链表 + 原地重排

var reorderList = function(head) {
    // 复制一个链表, 然后翻转, 然后根据中点截断, 可以写一写
    // 第一次遍历, 构造出双向链表, 遍历到最后一个节点之后, 反过来拼接, 下一个和前一个相等, 就结束
    const dummy = new Node(0);
    dummy.next = head;

    // 构造出双向链表
    let prev = dummy;
    let cur = head;

    while (cur !== null) {
        cur.prev = prev;
        prev = cur;
        cur = cur.next;
    }

    // 遍历完之后 prev 在最后一个节点上
    let high = prev;
    let low = head;

    // 奇数个节点 和 偶数个节点 结束的条件不同
    while (high !== low && high !== low.next) {
        const next = low.next;
        low.next = high;
        high = high.prev;
        low.next.next = next;
        low = next;
    }

    // 断开环
    high.next = null;

    return dummy.next;

};

方案三: 数组

先转换成数组, 然后按照指定顺序访问节点, 重新拼接即可

指针 i 从头向尾，指针 j 从尾向头，重新组装链表